package stack.programs.bad;

// ORIGINAL VERSION:
//Copyright � 2002�2010, Robert Sedgewick and Kevin Wayne. 
//Last updated: Tue Aug 14 11:15:04 EDT 2012.
//From: http://algs4.cs.princeton.edu/13stacks/Stack.java.html

import java.util.Iterator;
import java.util.NoSuchElementException;

import stack.programs.Stack;

//Properties a Stack implementation needs to have to be correct:
// 1: LIFO 
// 2.1: popping the Stack with pop() returns the element last added
// 2.2: popping the Stack with pop() removes the element last added
// 3.1: looking at the Stack with peek() returns the element last added
// 3.2: looking at the Stack with peek() does not remove the element last added
// 4.1: pushing onto the Stack with push(item) changes the top element into the item
// 4.2: pushing onto the Stack with push(item) moves the old last pushed item down the stack one.
// 5: size() must return the amount of elements in the Stack
// 6: check() must make sure all internal invariants are still there:
// 6.1: an empty stack has no first element
// 6.2: a stack of size one has one element
// 6.3: a stack larger than size one has more than one element
// 7: isEmpty() is only true if the stack size is also 0

public class StackBreakingProperty1And2<Item> implements Stack<Item> {
	private int N;          // size of the stack
    private Node first;     // top of stack

    // helper linked list class
    private class Node {
        private Item item;
        private Node next;
    }

   /**
     * Create an empty stack.
     */
    public StackBreakingProperty1And2() {
        first = null;
        N = 0;
        assert check();
    }

   /**
     * Is the stack empty?
     */
    public boolean isEmpty() {
        return first == null;
    }

   /**
     * Return the number of items in the stack.
     */
    public int size() {
        return N;
    }

   /**
     * Add the item to the stack.
     */
    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
        assert check();
    }

   /**
     * Delete and return the item most recently added to the stack.
     * @throws java.util.NoSuchElementException if stack is empty.
     */
    public Item pop() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        Item item = first.item;        // save item to return
        first = first.next;            // delete first node
        N--;
        //assert check();
        return first.next.item;        // return something else entirely!
    }


   /**
     * Return the item most recently added to the stack.
     * @throws java.util.NoSuchElementException if stack is empty.
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        return first.item;
    }

   /**
     * Return string representation.
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this)
            s.append(item + " ");
        return s.toString();
    }
       

    // check internal invariants
    private boolean check() {
        if (N == 0) {
            if (first != null) return false;
        }
        else if (N == 1) {
            if (first == null)      return false;
            if (first.next != null) return false;
        }
        else {
            if (first.next == null) return false;
        }

        // check internal consistency of instance variable N
        int numberOfNodes = 0;
        for (Node x = first; x != null; x = x.next) {
            numberOfNodes++;
        }
        if (numberOfNodes != N) return false;

        return true;
    } 


   /**
     * Return an iterator to the stack that iterates through the items in LIFO order.
     */
    public Iterator<Item> iterator()  { return new ListIterator();  }

    // an iterator, doesn't implement remove() since it's optional
    private class ListIterator implements Iterator<Item> {
        private Node current = first;
        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next; 
            return item;
        }
    }
}

